587. Erect the Fence

https://leetcode.com/problems/erect-the-fence/

題目解釋

你有n棵樹的座標，請你用柵欄把樹全部圍起來，因為柵欄太貴了所以請圍出最短的距離

這題簡單來說就是凸包(convex hull)的問題

解法1:

這個解法是Jarvis' March又叫做禮物包裝演算法(Gift Wrapping Algorithm)，概念是先找出最外側的任意點，之後用外積找出其他也是最外側的點，總之先上程式碼吧!

程式碼:

class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:

        if len(trees) <= 3:
            return trees
        
        start = self.find_start_pos(trees)
        hull = []
        p = start
        q = 0
        
        while True:
            
            q = (p + 1) % len(trees)
            
            for i in range(len(trees)):
                if self.orientation(trees[p], trees[i], trees[q]) < 0: 
                # i在逆時鐘方向，可以當作最外圈的候選
                    q = i
            
            for i in range(len(trees)):
                if i != p and i != q and self.orientation(trees[p], trees[i], trees[q]) == 0: 
                # 同一條線上
                    x = trees[p][0] <= trees[i][0] and trees[i][0] <= trees[q][0] \
                            or trees[p][0] >= trees[i][0] and trees[i][0] >= trees[q][0]
                    y = trees[p][1] <= trees[i][1] and trees[i][1] <= trees[q][1] \
                            or trees[p][1] >= trees[i][1] and trees[i][1] >= trees[q][1]
                    
                    if x and y:
                        hull.append(trees[i]);
                    
            hull.append(trees[q])
            p = q
            
            if p == start:
                break
        
        return hull
    
    def find_start_pos(self, trees):
        # 找起始的點
        start = 0
        for i, tree in enumerate(trees):
            if math.sqrt(tree[0]**2 + tree[1]**2) < math.sqrt(trees[start][0]**2 + trees[start][1]**2):
                start = i
                
        return start
    
    def orientation(self, p, q, r):
        #外積
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]) 

步驟:

1. 先找出任意最外側的點，因為這題已經限制 x,y 不會有負數了，所以我找最接近 (0,0) 的當起始點 p0
2. 找起始點以外的第二個點 p1 ，接著用迴圈讓所有點輪流當第三個點p2，用 (p0,p1) 的向量和 (p1,p2) 的向量做外積，判斷p2是不是逆時鐘方向的點；簡單來說就是看 p2 是不是在 (p0,p1) 向量右邊
3. 找到p2後，檢查是不是有點在 p0、p2 之間，是的話也要存起來

但是Time Limit Exceeded

這個方法的時間複查度是 O(mn)，m代表最外圈有幾個點，如果最外圈點很多的話就會超過系統限制的時間

閒聊:

今天的題目對我來說很難，之前沒有接觸過凸包的問題，所以學到新東西了

解法1的時間會超過系統要求的限制，所以要用其他的演算法

但是，我懶了

過幾天後再補上OK的解法吧!